Word Break II

LeetCode 140 | Difficulty: Hard

Hard

Problem Description

Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Example 1:

Input: s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
Output: ["cats and dog","cat sand dog"]

Example 2:

Input: s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]
Output: ["pine apple pen apple","pineapple pen apple","pine applepen apple"]
Explanation: Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: []

Constraints:

- `1 <= s.length <= 20`

- `1 <= wordDict.length <= 1000`

- `1 <= wordDict[i].length <= 10`

- `s` and `wordDict[i]` consist of only lowercase English letters.

- All the strings of `wordDict` are **unique**.

- Input is generated in a way that the length of the answer doesn't exceed 10^5.

Topics: Array, Hash Table, String, Dynamic Programming, Backtracking, Trie, Memoization

---

Approach

Dynamic Programming

Break the problem into overlapping subproblems. Define a state (what information do you need?), a recurrence (how does state[i] depend on smaller states?), and a base case. Consider both top-down (memoization) and bottom-up (tabulation) approaches.

When to use

Optimal substructure + overlapping subproblems (counting ways, min/max cost, feasibility).

Backtracking

Explore all candidates by building solutions incrementally. At each step, choose an option, explore further, then unchoose (backtrack) to try the next option. Prune branches that can't lead to valid solutions.

When to use

Generate all combinations/permutations, or find solutions that satisfy constraints.

Hash Map

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

Trie (Prefix Tree)

Build a tree where each edge represents a character, and paths from root represent prefixes. Enables O(L) prefix lookups where L is the word length.

When to use

Prefix matching, autocomplete, word search, longest common prefix.

String Processing

Consider character frequency counts, two-pointer approaches, or building strings efficiently. For pattern matching, think about KMP or rolling hash. For palindromes, expand from center or use DP.

When to use

Anagram detection, palindrome checking, string transformation, pattern matching.

---

Solutions

Solution 1: C# (Best: 300 ms)

Metric	Value
Runtime	300 ms
Memory	32.7 MB
Date	2020-10-23

Solution

public class Solution {
    public IList<string> WordBreak(string s, IList<string> wordDict)
{
    Dictionary<string, List<string>> memo = new Dictionary<string, List<string>>();
    return WordBreak(s, wordDict, memo);
}

public IList<string> WordBreak(string s, IList<string> wordDict, Dictionary<string, List<string>> memo)
{
    if (memo.ContainsKey(s)) return memo[s];
    List<string> result = new List<string>();
    if (s.Length == 0)
    {
        result.Add("");
        return result;
    }
    foreach (var word in wordDict)
    {
        if (s.StartsWith(word))
        {
            var subResults = WordBreak(s.Substring(word.Length), wordDict, memo);
            foreach (var val in subResults)
            {
                result.Add(word + (val==""?"":" "+val));
            }
        }
    }
    memo[s] = result;
    return result;
}
}

---

Complexity Analysis

Approach	Time	Space
Dynamic Programming	$O(n)$	$O(n)$
Backtracking	$O(n! or 2^n)$	$O(n)$
Hash Map	$O(n)$	$O(n)$
Trie	$O(L × n)$	$O(L × n)$

---

Interview Tips

Key Points

• Break the problem into smaller subproblems. Communicate your approach before coding.
• Define the DP state clearly. Ask: "What is the minimum information I need to make a decision at each step?"
• Consider if you can reduce space by only keeping the last row/few values.
• Hash map gives O(1) lookup — think about what to use as key vs value.
• Identify pruning conditions early to avoid exploring invalid branches.